レッスン3へようこそ 人工知能の概念（PolyU COMP5511）。このセッションでは、単一エージェントの経路探索から 敵対的探索へ移行します。ここではエージェントが競争的なマルチエージェント環境で動作します。さらに 制約充足問題（CSP）というパラダイムも紹介します。これは、経路ではなく、特定の制約群を満たす状態を見つけることを目的とするものです。

主要概念

• 敵対的探索： 賢い対戦相手に対して合理的な判断を下すための ミニマックス や アルファ・ベータ枝刈り などのアルゴリズムに焦点を当てます。
• モンテカルロ木探索（MCTS）： 確率的な意思決定を探求し、以下のような現代ゲームAIの中核を担います： AlphaGo。
• 制約充足： 変数、領域、制約を用いて問題をモデル化し、 バックトラッキング や 局所探索。

複雑性分析

敵対的設定では、探索空間の複雑性はしばしばゲームの分岐係数 $b$ と深さ $d$によって定義され、計算コストは次のようになります： $$O(b^d)$$ この指数関数的な増大により、アルファ・ベータ枝刈りのような効率的な枝刈り戦略が必要となります。